package com.hr.剑指offer.work2.list;

import java.util.Stack;

/**
 * @author ：zhz
 * @date ：Created in 2020/12/08
 * @version: V1.0
 * @slogan: 天下风云出我辈，一入代码岁月催
 * @description: 反转链表
 **/
public class ReverseList_206 {
    //一、利用栈实现
    public ListNode reverseList(ListNode head) {
        ListNode cur=head;
        Stack<Integer> stack=new Stack<>();
        while (cur!=null){
            stack.add(cur.val);
            cur=cur.next;
        }
        cur=head;
        while(!stack.isEmpty()){
            cur.val = stack.pop();
            cur=cur.next;
        }

        return head;
    }
    /**
     * 二、利用递归实现：我子节点下的所有节点都已经反转好了，
     * 现在就剩我和我的子节点 没有完成最后的反转了，所以反转一下我和我的子节点。
     */

    public ListNode reverseList1(ListNode head) {
        if (head==null || head.next==null){
            return head;
        }
        ListNode cur = reverseList1(head.next);
        head.next.next=head;
        head.next=null;
        return cur;
    }

    //三、双指针
    public ListNode reverseList3(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        ListNode temp=null;
        while (cur!=null){
            temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
}
